home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / pardemos / war.icl < prev   
Text File  |  1992-08-07  |  4KB  |  111 lines
  1. MODULE war;
  2.  
  3. <<
  4. Parallel version of Warshall's shortest path algorithm
  5.  
  6. Calculates the lenghts of the shortest paths between all nodes of
  7. a directed graph represented by its adjacency matrix using Warshall's
  8. algorithm.
  9. The result of the program will be a matrix containing the
  10. length of the shortest path between node i and node j on index (i,j).
  11. Strictness annotations were added because the strictness analyzer doesn't
  12. derive strictness information from parallel functions, because that could
  13. lead to unexpected and unwanted results.
  14.  
  15. Run the program with the show constructors option on.
  16. >>
  17.  
  18. IMPORT deltaI;
  19.  
  20.  
  21. TYPE
  22.  
  23. ::  Row -> [INT];   == A row is a list of integers.
  24. ::  Mat -> [Row];   == A graph is represented as a matrix: a list of rows.
  25.  
  26.  
  27. MACRO
  28.  
  29.     Size -> 6;      == The size of the initial matrix (= the number of nodes
  30.                     == of the initial graph).
  31.     
  32.  
  33. RULE
  34.  
  35. ==  The initial matrix.
  36.  
  37. ::  InitMat -> Mat;                             ==   Shortest path matrix:
  38.     InitMat ->  [[  0,100,100, 13,100,100  ],   == [  0, 16,100, 13, 20, 20 ]
  39.                 [ 100,  0,100,100,  4,  9  ],   == [ 19,  0,100,  5,  4,  9 ]
  40.                 [  11,100,  0,100,100,100  ],   == [ 11, 27,  0, 24, 31, 31 ]
  41.                 [ 100,  3,100,  0,100,  7  ],   == [ 18,  3,100,  0,  7,  7 ]
  42.                 [  15,  5,100,  1,  0,100  ],   == [ 15,  4,100,  1,  0,  8 ]
  43.                 [  11,100,100, 14,100,  0 ]];   == [ 11, 17,100, 14, 21,  0 ]
  44.  
  45.  
  46. ==  Miscellaneous functions.
  47.  
  48. ::  Min INT INT -> INT;
  49.     Min i j -> j, IF > i j
  50.             -> i;
  51.  
  52. ::  Select [x] INT -> x;
  53.     Select [h|t] 1 -> h;
  54.     Select [h|t] i -> Select t (-- i);
  55.  
  56. ::  Last [x] -> x;
  57.     Last [last] -> last;
  58.     Last [head|tail] -> Last tail;
  59.     
  60. ::  Tail [x] -> [x];
  61.     Tail [h|t] -> t;
  62.  
  63.  
  64. <<  Warshall's shortest path algorithm. A cycle of n (= Size) processes
  65.     will be created, one process for each row of the matrix. These processes
  66.     communicate their final result to a collection process.
  67. >>
  68.  
  69. ::  PWarshall Mat -> Mat;
  70.     PWarshall initmat -> finalmat,
  71.                          (finalmat,lastrow): RowProc 1 initmat lastrow;
  72.  
  73. ::  RowProc INT Mat Mat -> (Mat,Mat);
  74.     RowProc k [row_n] left
  75.         -> ([chan1], chan2),
  76.             chan1: {I} Last chan2,
  77.             chan2: {I} Iterate k 1 row_n left;
  78.     RowProc k [row_k|restmat] left
  79.         -> ([chan1 | nextrows], lastrow),
  80.             chan1: {I} Last chan2,
  81.             chan2: {I} Iterate k 1 row_k left,
  82.             (nextrows,lastrow): {P} RowProc !(++ k) restmat chan2;
  83.                                                 
  84. ::  Iterate INT INT Row Mat -> Mat;
  85.     Iterate k i row_k left  -> [row_k]              , IF < Size i
  86.                             -> Next k i row_k left  , IF = k i
  87.                             -> Update k i row_k left;
  88.  
  89. ::  Next INT INT Row Mat -> Mat;
  90.     Next k i row_k left
  91.         -> [row_k | nextit],
  92.            nextit: {I} Iterate k (++ i) row_k (Tail left);
  93.  
  94. ::  Update INT INT Row Mat -> Mat;
  95.     Update  k i row_k [row_i | tlleft]
  96.         -> [row_i | update],
  97.            update:    {I} Iterate k (++ i) upd_row_i tlleft,
  98.            upd_row_i: ! UpdRow row_k row_i k_to_i,
  99.            k_to_i:    Select row_k i;
  100.  
  101. ::  UpdRow Row Row INT -> Row;
  102.     UpdRow [] rowi j_to_i -> [];
  103.     UpdRow [j_to_k | rowj]  [i_to_k | rowi]  j_to_i
  104.         -> [! Min j_to_k (+ j_to_i i_to_k) | ! UpdRow rowj rowi j_to_i];
  105.  
  106.  
  107. ==  The Start rule: apply Warshall's algorithm on the initial matrix.
  108.  
  109. ::  Start -> Mat;
  110.     Start -> PWarshall InitMat;
  111.